package com.chj.leetcode.tijie400to450;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Code406_QueueReconstructionByHeight {
	public int[][] reconstructQueue(int[][] people) {
		if (people == null || people.length <= 1) {
			return people;
		}

		/*
		 * 按照 如下规则，给数组排序： 若两人身高相等，将 p[1]小的 排在前面(这样才能保证 后面的p[1]条件满足) 若两人身高不等，将 身高高的 排在前面
		 */
//		Arrays.sort(people, (p1, p2) -> {
//			return p1[0] == p2[0] ? p1[1] - p2[1] : p2[0] - p1[0];
//		});
		Arrays.sort(people, new Comparator<int[]>() {
			public int compare(int[] person1, int[] person2) {
				if (person1[0] != person2[0]) {
					return person2[0] - person1[0];
				} else {
					return person1[1] - person2[1];
				}
			}
		});

		/*
		 * 根据 排在当前人前面的、比当前人高的 人数，将 所有人放入list中 由于上面的排序，导致
		 * 我们放置后的list中：k值大的排在k值小的后面，k值相同的：身高高的排在身高低的后面
		 * 高个子先站好位，矮个子插入到K位置上，前面肯定有K个高个子，矮个子再插到前面也满足K的要求
		 */
		List<int[]> list = new ArrayList<>();
		for (int[] person : people) {
			list.add(person[1], person);
		}

		return list.toArray(people);
	}

//	作者：leetcoder-youzg
//	链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/java-san-bu-jie-jue-shen-gao-zhong-jian-dui-lie-we/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
